#!/usr/bin/python
# Filename: Path.py

# Path in Graph(directed graph)

# Dijkstra Algorithm: shortest path from 1 vertex s to all other vertexes
# two group:
# a) vertexes which are already have shortest path
# b) vertexes which not
# initiate path of s to 0 and all other vertex to infinite
# Algorithm:
# a) select vertex i of shortest path in b
# b) add i to a, mark i visited, update path of j in b if <i, j> is an edge
# b.1) if path j > path i + weight<i, j>, path j = path i + weight<i, j>
# b.2) also update j's pre-node in order to find the shortest path
# c) repeat, until there's no vertex of shortest path in b(b is empty or all infinite)
# time complexity:
# a) select vertex i of shortest path in b
# a.1) pure comparation - O(n)
# a.2) min-heap - O(log(n)), with min-heap initiate O(n)
# total O(n^2) or O(nlog(n)) + O(n)
# b) update: O(e) * O(log(n), update every node leads to update of min-heap
# total cost = O((e+n)Iog(n))

# Floyd Algorithm: shortest path from 1 vertex i to another vertex j
# Floyd algorithm recursively generate a sequence of matrix from adjacent matrix,
# adj(k)[i, j] is shortest path from i to j which inner vertex less than k,
# caution, nodes start from No. 1.
# when adj(k-1), select shorter:
# a) adj(k)[i, j] = adj(k-1)[i, j](the shortest path is not through k)
# b) adj(k)[i, j] = adj(k-1)[i, j] + adj(k-1)[j, k]
# c) pre[i, j] = k if b(initiate pre[i, j] with i if adj(0)[i, j] != infinite, or else with 0) 
# time complexity:
# |N|^3, each select coust |N|^2

# Prim Algorithm: Minimum-cost Spanning Tree(MST)
# add 1 node to MST, add all its adjacent edges to A(can be min-heap)
# a) select 1 edge e which is lightest weighted in A and remove it from A
# b) add e and node of e i which is not in MST(visited) to MST, set i as visited
# c) add all edges adjacent i except e to A
# d) repeat, until add all nodes to MST
# !!!pay attention to prove of Prim algorithm
# time complexity:
# similar to Dijkstra algorithm
# a) select and remove cost O(log(e)) in min-heap
# b) add e and i O(1), to decide which node is i, just see whether it's visited
# c) add edges cost total O(e*log(e))
# d) repeat n times
# total cost = n*log(e) + e*log(e)

# Kruskal Algorithm: Minimum-cost Spanning Tree
# divide all nodes into n equivalence classes
# a) select and remove e(<i, j>) from edges(min-heap)
# b) if i and j are not in same equivalence classed, add e to MST, merge equivalence classes
# c) repeat, until only 1 equivalence class is left(record number of equivalence class)
# time complexity:
# a) build min-heap cost O(e)
# b) select e cost total O(e*log(e))(min-heap sort)
# c) merge equivalence class cost total O(n)
# total cost = O(e*log(e))
